package com.zjsru.plan2023.oneday;

/**
 * @Author: cookLee
 * @Date: 2023-09-13
 * 检查骑士巡视方案
 */
public class CheckValidGrid {

    /**
     * 输入：grid = [[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]]
     * 输出：true
     * 解释：grid 如上图所示，可以证明这是一个有效的巡视方案。
     * \
     * 输入：grid = [[0,3,6],[5,8,1],[2,7,4]]
     * 输出：false
     * 解释：grid 如上图所示，考虑到骑士第 7 次行动后的位置，第 8 次行动是无效的。
     * \
     * 从左上角开始能不能按照 “日“字形走完全程
     *
     * @param args
     */
    public static void main(String[] args) {
        CheckValidGrid checkValidGrid = new CheckValidGrid();
        int[][] grid = new int[][]{{0,11,16,5,20},{17,4,19,10,15},{12,1,8,21,6},{3,18,23,14,9},{24,13,2,7,22}};
        System.out.println(checkValidGrid.checkValidGrid(grid));
    }

    /**
     * 模拟
     *
     * @param grid
     * @return boolean
     */
    public boolean checkValidGrid(int[][] grid) {
        //如果左上角第一位开始不是0直接返回false
        if (grid[0][0] != 0) {
            return false;
        }
        //记录数字在网格中的位置
        int[][] instructions = new int[grid.length * grid.length][2];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid.length; j++) {
                //instructions[1][0] 存储行号 ，instructions[1][1] 存储列号
                instructions[grid[i][j]][0] = i;
                instructions[grid[i][j]][1] = j;
            }
        }
        //两个相邻数字的位置差的绝对值在水平和垂直方向上都为2
        for (int i = 1; i < grid.length * grid.length; i++) {
            int x = Math.abs(instructions[i][0] - instructions[i - 1][0]);
            int y = Math.abs(instructions[i][1] - instructions[i - 1][1]);
            //不是不等于2 说明数字隔得位置不是”日“字形
            if (x * y != 2) {
                return false;
            }
        }
        return true;
    }


}
